package 题目集.bfs.bfs建图;

import org.junit.Test;

import java.util.*;

/**
 * https://leetcode.cn/problems/word-ladder-ii/description/
 */
public class 带路径的bfs {

    static Set<String> wordSet;             //没有被走过的节点
    static Set<String> currLevel;           //当前层的节点
    static Set<String> nextLevel;           //下一层的节点
    static List<List<String>> res;
    static Map<String, List<String>> preMap;    //记录前驱节点有哪些
    static int level;   //最短路径的层数
    static String[] path;

    /**
     * 思路：
     *      1.通过bfs找到最短路径，在bfs记录下一个节点的前驱节点
     *      2.通过dfs找到所有路径
     */
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        build(wordList);
        if (bfs(beginWord, endWord)) {
            path = new String[level];
            dfs(level - 1, endWord);
        }
        return res;
    }

    public void build(List<String> wordList) {
        wordSet = new HashSet<>(wordList);
        currLevel = new HashSet<>();
        nextLevel = new HashSet<>();
        res = new ArrayList<>();
        preMap = new HashMap<>();
        level = 0;
    }

    /**
     * 构建图，并返回是否能够抵达终点
     * @return
     */
    public static boolean bfs(String s, String e) {
        currLevel.add(s);
        while (!currLevel.isEmpty()) {
            level++;
            wordSet.removeAll(currLevel);   //标记已走过
            for (String cur : currLevel) {
                if (e.equals(cur)) return true;   //当前层是终点层
                char[] chars = cur.toCharArray();
                for (int i = 0; i < chars.length; i++) {
                    char old = chars[i];
                    for (char c = 'a'; c <= 'z'; c++) {
                        chars[i] = c;
                        String next = new String(chars);
                        if (wordSet.contains(next)) {
                            nextLevel.add(next);
                            List<String> pre = preMap.get(next);
                            if (pre == null) {
                                pre = new ArrayList<>();
                                preMap.put(next, pre);
                            }
                            pre.add(cur);
                        }
                    }
                    chars[i] = old;
                }
            }
            currLevel = nextLevel;
            nextLevel = new HashSet<>();
        }
        return false;
    }

    /**
     * 构建到起点的路径
     */
    public static void dfs(int i, String cur) {
        List<String> pre = preMap.get(cur);
        if (pre == null) {  //抵达起点
            path[i] = cur;
            res.add(Arrays.asList(path.clone()));
            return;
        }
        path[i] = cur;
        for (String next : pre) {
            dfs(i - 1, next);
        }
    }

    @Test
    public void test() {
        String[] words = {"hot", "dot", "dog", "lot", "log", "cog"};
        System.out.println(findLadders("hit", "cog", Arrays.asList(words)));
    }
}
